#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>

struct Block {
    int _id;             //分区的序号
    int _size;           //分区的大小
    int _startAddr;      //分区的开始位置
    bool _status;        //分区的状态：true为空闲，false为被占用
    int _pid;            //如果该分区被占用，则存放占用进程的id; 否则为-1

    Block(int id, int startAddr, int size)
        : _id(id)
        , _startAddr(startAddr)
        , _size(size)
        , _status(true)
        , _pid(-1)
    {}

    Block(int id, int startAddr, int size, int pid)
        : _id(id)
        , _startAddr(startAddr)
        , _size(size)
        , _status(true)
        , _pid(pid)
    {}
};

struct PCB {
    int _pid;            //进程的序号
    int _neededMem;      //需要的内存分区大小
    int _status;         //1: 内存分配成功；-1：分配失败；0：还未分配
    int _blockID;        //如果分配成功，保存占用分区的id,否则为-1

    PCB(int pid, int neededMem)
        : _pid(pid)
        , _neededMem(neededMem)
        , _status(0)
        , _blockID(0)
    {}
};

#define MEOMERYSIZE 1024
#define PROCESSNUM  10


class DPMAllocation {
private:
    void GenerateProcess() {
        for (int i = 0; i < PROCESSNUM; i++) {
            int neededMem = rand() % 101 + 100;
            _pcbs.emplace_back(i, neededMem);
        }
        printf("    ProcID neededMem\n");
        for (auto& pcb : _pcbs)
            printf("     %5d %9d\n", pcb._pid, pcb._neededMem);
        std::cout << "****************************************************" << std::endl;

        _free_blocks.emplace_back(_blockID, 0, MEOMERYSIZE);
        printf("FreeBlkID StartAddr    Size\n");
        printf("%9d %9d    %4d\n", 0, 0, MEOMERYSIZE);
        std::cout << "****************************************************" << std::endl;
    }

    void ShowFreeBlk_UsedBlk() {
        printf("FreeBlkID StartAddr    Size\n");
        for (auto& block : _free_blocks)
            printf("%9d %9d    %4d\n", block._id, block._startAddr, block._size);

        if (!_used_blocks.empty()) {
            std::cout << "\n";
            printf("UsedBlkID StartAddr    Size    ProcID\n");
            for (auto& block : _used_blocks)
                printf("%9d %9d    %4d    %6d\n", block._id, block._startAddr, block._size, block._pid);
        }
        std::cout << "****************************************************" << std::endl;

    }


    void MeomeryAllocationFirstFit() {
        // 分别取出一个进程
        for (auto& pcb : _pcbs) {
            // 在freeblock中查找是否存在合适大小的空间
            printf("Allocating memory for process %d, memory requirement = %d\n", pcb._pid, pcb._neededMem);
            auto it = _free_blocks.begin();
            for (; it != _free_blocks.end(); ++it)
                if (it->_size >= pcb._neededMem)
                    break;
            if (it == _free_blocks.end()) {
                printf("Memory allocation failed for process %d !\n", pcb._pid);
                pcb._status = -1;
                ShowFreeBlk_UsedBlk();
                continue;
            }
            pcb._status = 1;
            // 当前it指向的内存块有足够的空间，开始随机化分配
            // 一共存在三种情况。分成三个区间，分成两个区间，刚好一个区间

            // 当it->size == neededMem的时候出现摸零的情况
            int addr;
            if (it->_size != pcb._neededMem)
                addr = rand() % (it->_size - pcb._neededMem) + it->_startAddr;
            // 刚好一个区间
            if (it->_size == pcb._neededMem) {
                Block total(it->_id, it->_startAddr, it->_size, pcb._pid);
                _free_blocks.erase(it);
                _used_blocks.emplace_back(total);
                pcb._blockID = total._id;
                ShowFreeBlk_UsedBlk();
                continue;
            }
            else if (addr == it->_startAddr || addr + pcb._neededMem == it->_size) {
                // 分成了左右两个区间[addr, addr + it->size][]
                // 将左边分配出去
                if (addr == it->_startAddr) {
                    Block left(it->_id, addr, pcb._neededMem, pcb._pid);
                    Block right(_blockID + 1, it->_startAddr + pcb._neededMem, it->_size - pcb._neededMem);
                    _free_blocks.insert(it, right);
                    _free_blocks.erase(it);
                    _used_blocks.emplace_back(left);
                    pcb._blockID = left._id;
                }
                else {
                    // 将右边分配出去
                    Block left(it->_id, it->_startAddr, it->_size - pcb._neededMem);
                    Block right(_blockID + 1, addr, pcb._neededMem, pcb._pid);
                    _free_blocks.insert(it, left);
                    _free_blocks.erase(it);
                    _used_blocks.emplace_back(right);
                    pcb._blockID = right._id;
                }
                _blockID++;
                ShowFreeBlk_UsedBlk();
                continue;
            }

            // [it->_startAddr addr - it->_startAddr][addr neededMem][addr+neededMem it->_startAddr + it->_size - addr - pcb._neededMem]
            Block left(it->_id, it->_startAddr, addr - it->_startAddr);
            Block right(_blockID + 1, addr + pcb._neededMem, it->_startAddr + it->_size - addr - pcb._neededMem);
            Block middle(_blockID + 2, addr, pcb._neededMem, pcb._pid);
            pcb._blockID = middle._id;

            _blockID += 2;

            _used_blocks.emplace_back(middle);
            // 现在将left和right插入到应该插入的地方
            _free_blocks.insert(it, { left, right });
            _free_blocks.erase(it);

            ShowFreeBlk_UsedBlk();
        }
    }

    void CombineUsed_Free() {
        auto ublock = _used_blocks.front();
        printf("Recycling used memory block for process %d\n", ublock._pid);
        auto fit = _free_blocks.begin();
        for (; fit != _free_blocks.end(); ++fit) {
            if (fit->_startAddr + fit->_size == ublock._startAddr 
                || ublock._startAddr + ublock._size == fit->_startAddr)
                break;
        }
        if (fit == _free_blocks.end()) {
            // 将其插入到freeblock中
            fit = _free_blocks.begin();
            for (; fit != _free_blocks.end(); ++fit) {
                if (fit->_startAddr >= ublock._startAddr + ublock._size)
                    break;
            }
            _free_blocks.insert(fit, ublock);
        } else {
            if (fit->_startAddr + fit->_size == ublock._startAddr)
                fit->_size += ublock._size;
            else
                fit->_size += ublock._size, fit->_startAddr = ublock._startAddr;
        }
        _used_blocks.pop_front();
        ShowFreeBlk_UsedBlk();
    }

    void CombineFreeBlock() {
        // 组合之后在打印
        auto& fblock = _free_blocks.front();
        auto it = _free_blocks.begin();
        auto next = ++it;
        fblock._size += next->_size;
        Block blk(fblock);
        _free_blocks.pop_front();
        _free_blocks.pop_front();
        _free_blocks.push_front(std::move(blk));
        ShowFreeBlk_UsedBlk();
    }

    void MeomeryRecycle() {
        while (_free_blocks.size() != 1 || !_used_blocks.empty()) {
            if (!_used_blocks.empty())
                CombineUsed_Free();
            else
                CombineFreeBlock();
        }
    }

    void MeomeryAllocationNextFit() {
        // 设置起始查询指针，用于指示下一次起始查询的空闲分区
        // 最后一个分区大小不满足的时候，回到第一个空闲分区
        // 每次从上一次找到的下一个开始查找

        auto fit = _free_blocks.begin();
        // 分别取出一个进程
        for (auto& pcb : _pcbs) {
            // 在freeblock中查找是否存在合适大小的空间
            printf("Allocating memory for process %d, memory requirement = %d\n", pcb._pid, pcb._neededMem);

            // 这里需要注意fit不能为end
            auto it = fit;

            if (it->_size < pcb._neededMem) {
                ++it;
                if (it == _free_blocks.end())
                    it = _free_blocks.begin();
                while (it->_id != fit->_id) {
                    // 从头开始找
                    if (it->_size >= pcb._neededMem)
                        break;
                    
                    ++it;
                    if (it == _free_blocks.end())
                        it = _free_blocks.begin();
                }
            }

            if (it->_id == fit->_id && it->_size < pcb._neededMem) {
                printf("Memory allocation failed for process %d !\n", pcb._pid);
                pcb._status = -1;
                ShowFreeBlk_UsedBlk();
                continue;
            }
            pcb._status = 1;
            // 当前it指向的内存块有足够的空间，开始随机化分配
            // 一共存在三种情况。分成三个区间，分成两个区间，刚好一个区间
            // 当it->size == neededMem的时候出现摸零的情况
            int addr;
            if (it->_size != pcb._neededMem)
                addr = rand() % (it->_size - pcb._neededMem) + it->_startAddr;
            // 刚好一个区间
            if (it->_size == pcb._neededMem) {
                Block total(it->_id, it->_startAddr, it->_size, pcb._pid);
                // 更新fit
                // int id = it->_id;
                // int needid = nextIteratorId(it);
                // fit = update_eraseIterator(id, needid);
                fit = it;
                ++fit;
                if (fit == _free_blocks.end())
                    fit = _free_blocks.begin();
                int id = fit->_id;
                _free_blocks.erase(it);
                // 防止迭代器失效，重新找一次
                fit = updateIterator(id);
                _used_blocks.emplace_back(total);
                pcb._blockID = total._id;

                ShowFreeBlk_UsedBlk();
                continue;
            }
            else if (addr == it->_startAddr || addr + pcb._neededMem == it->_size) {
                // 分成了左右两个区间[addr, addr + it->size][]
                // 将左边分配出去
                if (addr == it->_startAddr) {
                    Block left(it->_id, addr, pcb._neededMem, pcb._pid);
                    Block right(_blockID + 1, it->_startAddr + pcb._neededMem, it->_size - pcb._neededMem);
                    
                    // 当前id指向的是left，紧接着left的id为right
                    // 所以needid等于right.id
                    int id = it->_id;
                    int needid = right._id;

                    _free_blocks.insert(it, right);
                    fit = update_eraseIterator(id, needid);
                    _used_blocks.emplace_back(left);
                    pcb._blockID = left._id;
                }
                else {
                    // 将右边分配出去
                    Block left(it->_id, it->_startAddr, it->_size - pcb._neededMem);
                    Block right(_blockID + 1, addr, pcb._neededMem, pcb._pid);
                    int id = it->_id;

                    int needid = nextIteratorId(it);
                    _free_blocks.insert(it, left);
                    fit = update_eraseIterator(id, needid);
                    _used_blocks.emplace_back(right);
                    pcb._blockID = right._id;
                }
                _blockID++;
                ShowFreeBlk_UsedBlk();
                continue;
            }

            // [it->_startAddr addr - it->_startAddr][addr neededMem][addr+neededMem it->_startAddr + it->_size - addr - pcb._neededMem]
            Block left(it->_id, it->_startAddr, addr - it->_startAddr);
            Block right(_blockID + 1, addr + pcb._neededMem, it->_startAddr + it->_size - addr - pcb._neededMem);
            Block middle(_blockID + 2, addr, pcb._neededMem, pcb._pid);
            pcb._blockID = middle._id;

            _blockID += 2;

            _used_blocks.emplace_back(middle);
            // 现在将left和right插入到应该插入的地方
            // 现在left和it的id一样，修改将要删除的it的id
            it->_id = -2;
            _free_blocks.insert(it, { left, right });
            fit = update_eraseIterator(it->_id, right._id);
            ShowFreeBlk_UsedBlk();
        }
    }

    int nextIteratorId(std::list<Block>::iterator it) {
        if (_free_blocks.empty())
            return -1;
        auto itt = it;
        ++itt;
        if (itt == _free_blocks.end())
            itt = _free_blocks.begin();
        return itt->_id;
    }

    std::list<Block>::iterator updateIterator(int id) {
        auto it = _free_blocks.begin();
        for (; it != _free_blocks.end(); ++it) {
            if (it->_id == id)
                return it;
        }
        return std::list<Block>::iterator();
    }

    // 删除迭代器的同时，返回下一个迭代器
    std::list<Block>::iterator update_eraseIterator(int id, int needid) {
        auto it = _free_blocks.begin();
        for (; it != _free_blocks.end(); ++it) {
            if (it->_id == id)
                break;
        }
        _free_blocks.erase(it);
        // 返回it下一个的迭代器        
        return updateIterator(needid);
    }

public:
    DPMAllocation()
        : _blockID(0)
    {
        srand(time(nullptr));
        GenerateProcess();
    }

    void allocationFirstFit() {
        MeomeryAllocationFirstFit();
    }

    void allocationNextFit() {
        MeomeryAllocationNextFit();
    }

    void recycle() {
        MeomeryRecycle();
    }
private:
    std::list<PCB> _pcbs;
    std::list<Block> _free_blocks;
    std::list<Block> _used_blocks;
    size_t _blockID;
};
